'use strict';


const parenthesisMap = {
  0: [],
  1: ['()'],
};

const getParentthesis = function(n) {
  if (parenthesisMap[n]) {
    return parenthesisMap[n];
  }

  const finalSet = new Set();

  const subList = getParentthesis(n - 1);

  for(const pattern of subList) {
    finalSet.add(`(${pattern})`);
  }

  for(let i = 1; i < n; i++) {
    const left = i;
    const right = n - i;
    const leftList = getParentthesis(left);
    const rightList = getParentthesis(right);

    for(const leftPattern of leftList) {
      for(const rightPattern of rightList) {
        finalSet.add(`${leftPattern}${rightPattern}`);
      }
    }
  }

  parenthesisMap[n] = [...finalSet];
  return parenthesisMap[n];
}

/**
 * @param {number} n
 * @return {string[]}
 */
const generateParenthesis = function(n) {
  return getParentthesis(n);
};

const list = generateParenthesis(4);

console.log(list.length);
console.log(list);